https://introtcs.org/public/lec_02_representation.html#representing-objects-beyond-numbers

숫자 외의 다른 자료의 표현

encoding, decoding 함수를 각각 E,D라고 하자.
그러면 어떤 객체object를 표현하는 representation scheme은 (E,D)다.

E는 객체를 0,1의 유한길이 수열로, D는 0,1의 유한길이 수열을 각각 맵핑해주는 함수.
그리고 객체의 부분을 o라고 하고 모든 o 드리 o = D(E(o)) 여야 한다.
이게 D가 onto, 전사함수라는 것을 함의한다.
왜?
D의 정의역은 이진수열이다. o1,o2,o3 을 E가 00,01,10 으로 변환했다면 00,01,10을 각각 o들로 변환할 수 있겠지만 1001110은 변환할 o가 없다(부분함수).
그래서 정의역이 크기때문에 전사함수. 반대로 E는 단사함수다.

Finite representations

객체 O가 유한하다면, 수열은 유한한 길이 n을 가진다. n자리수 이진 수열의 경우의 수는 2^{n+1}-1개다.

S= {s0,s1,s2,....,sk} , T={t0,t1,t2,.....tm}
집합 S,T가 있고 E : S -> T 의 E가 단사함수라면, S의 크기가 T이하여야 한다.(정의상)
정의상 단사 함수는 자신의 정의역이 중복되지 않게 치역과 1:1 연결이 되어야 하니까.

Prefix-free encoding

prefix란?
y와 y가 있을때 y<=y면서 y의 i번째 까지 y의 i번째와 같으면 y는 y의 prefix다.
"Hello"와 "Hello,World"가 있으면 Hello가 prefix라는 말.

prefix-free?
말 그대로 prefix가 없는 상태를 의미한다. O의 부분들인 o를 E(o)했을 때, 어떤 E(o)도 E(o`)의 prefix가 아닐때.

prefix-free implies tuple encoding.

인코딩 함수 E가 객체 O를 이진수열로 변환하고 prefix-free하다면, 변환된 각 이진수열을 순서에 맞게 연결하는것과 똑같다.
o1,o2,o3의 E결과값이 각각 0,10,110 이면, E(o1,o2,o3) = E(o1)E(o2)E(o3) = 010110.
그리고 E(o1,o2,o3) 010110 과 1-1 관계일 수 밖에 없다.
왜?
간략하게 말하면 prefix가 없으니까 중복이 없어서 010110을 해독하면서 01/01/10인지 0/101/10인지 명확하지 않으니까. 명확하지 않음은 1-n관계.

prefix-free로 만들려면?

어떤건 자연스럽게 prefix-free상태일 수 있다. 가령 모든 인코딩 결과물의 길이가 똑같다면 어떤것도 다른 어떤것의 prefix가 되지 않는다.
prefix정의상 y가 y의 길이 이하이면서, y가 y를 완전히 포함해야 prefix가 된다. 그런데 모든 인코딩이 길이가 같으면서 어떤것이 prefix가 된다는건 두 인코딩이 동일하다는 것이고, 이건 인코딩 함수 E가 1-1 함수가 아니라는 것으로 인코딩 함수의 정의에 부합하지 않는다.

일단 앞에서 rational numbers를 변환했던것 처럼 0->00 으로 1->11로 하는 방법이 있다.
증명:

1. E가 1-1 함수이면서
2. E가 prefix-free라면 (사실 prefix-free라면 이미 1-1함수다.)

# takes functions encode and decode mapping
# objects to lists of bits and vice versa,
# and returns functions pfencode and pfdecode that
# maps objects to lists of bits and vice versa
# in a prefix-free way.
# Also returns a function pfvalid that says
# whether a list is a valid encoding
def prefixfree(encode, decode):
    def pfencode(o):
        L = encode(o)
        return [L[i//2] for i in range(2*len(L))]+[0,1]
    def pfdecode(L):
        return decode([L[j] for j in range(0,len(L)-2,2)])
    def pfvalid(L):
        return (len(L) % 2 == 0 ) and all(L[2*i]==L[2*i+1] for i in range((len(L)-2)//2)) and L[-2:]==[0,1]

    return pfencode, pfdecode, pfvalid

pfNtS, pfStN , pfvalidN = prefixfree(NtS,StN)

NtS(234)
# 11101010
pfNtS(234)
# 111111001100110001
pfStN(pfNtS(234))
# 234
pfvalidM(pfNtS(234))
# true

여러가지 인코딩들

문자 인코딩

ASCII 코드
아스키코드는 영어 알파벳을 포함한 128개 문자를 고정된 7비트 길이로 표현한다.
위에서 본것처럼 길이가 모두 동일한 인코딩은 자연히 Prefix-free다.

Unicode
UTF-8 방법을 사용해서 문자를 인코딩하는데, 이는 ASCII와 달리 가변 길이로 prefix-free를 구현해서 사용한다.

Vectors, matrices, images 인코딩

벡터는 숫자들의 리스트이고 메트릭스는 벡터의 리스트니까 당연히 이진수로 나타낼 수 있다.
이와 비슷하게 이미지는 모든 픽셀들이 가지고있는 rgb값을 저장하는 방식으로 인코딩할 수 있겠다.
하지만 효율적이지 않아서 잘 사용하지 않는다고. 많이 사용되는 JPEG방식은 이렇게 인코딩 하지 않는다.

그래프 인코딩

adjacency matrix로 표현하는 방법이 있다.
각 노드 0,1,2,3 이 각자 엣지를 리스트에 담고 그것들을 다시 리스트에 담는 방법.

[0,0,1,1] 0->2,3
[1,0,0,0] 1->0
[1,0,0,1] 2->0,3
[0,1,0,0] 3->1

근데 이걸 똑같이 다음과 같이 담을수 도 있다.
adjacency list로

[2,3]
[0]
[0,3]
[1]

둘의 차이가 중요할 수 있다고 하는데 교재에서는 다루지 않겠다고 한다.
대표적으로 해당하는 엣지가 있는지 조회할 때에는 리스트 방법이 불리하다 : 행렬의 경우 matrix[i][j]로 한번에 조회 가능. 1 or 0. 그러나 리스트에서는 i가 가지고 있는 엣지들을 다 조회해서 j가 있는지 확인해야한다.

Computational tasks

컴퓨팅, 그러니까 computational process란 입력 -> 출력 을 실행하는 일종의 함수다.

specification, implementation

(mathematical functions 과 algorithms/programs 분리.)
컴퓨팅에 대해서 애기할 때 크게 두 가지의 주제가 있다.

1. 입력 -> 출력을 어떻게 맵핑할 것인가?
2. 그리고 그걸 어떻게 구현할 것인가
   둘 다 "어떻게"라는 질문을 하지만 분명히 구분된다.
   그래서 mathematical function 과 algorithm의 분리라고도 한다.

1번은 수학적인 의미로 '함수'에 대해서 묻는 질문이다. 그니까 컴퓨터가 어떤 수학 함수를 실행해야 되는지를, 즉 computational task를 묻는것이다.
(2,3) -> 6, (3,4) ->12, (4,5)->20 은 입력된 두 수를 곱한 결과의 자연수와 맵핑하는 함수다.
너무 간단해서 잘 안보이지만 어쨋든 'm과n을 곱하기' 가 임무고,
그걸 구현하는 방법은 m을 n번 더하기, 혹은 교재 앞에서 나왔던 방법(grade-school algorithm)이 있다. (이게 전부는 아님. 더 있다.)

def mult1(x,y):
  res = 0
  while y>0:
    res += x
    y -= 1
  return res

def mult2(x,y):
  a = str(x) # represent x as string in decimal notation
  b = str(y) # represent y as string in decimal notation
  res = 0
  for i in range(len(a)):
    for j in range(len(b)):
      res += int(a[len(a)-i])*int(b[len(b)-
        j])*(10**(i+j))↪
  return res

print(mult1(12,7))
# 84
print(mult2(12,7))
# 84

3과 4를 가지고 12를 만들어내려면 어떤what 함수가 필요한지 알아야하고(specification)
그걸 어떻게how 구현하는지 알아야한다(implementation).